package OtrosTPs.TP1;

import java.util.ArrayList;

public class LevenshteinDistance {

    public static void main(String[] args) {
        ArrayList<String> cadenas = new ArrayList<String>();

//        cadenas.add("Pablo");
//        cadenas.add("Susana");
//        cadenas.add("Roberto");
//        cadenas.add("Florencia");

        cadenas.add("Alan");
        cadenas.add("Zulma");
        cadenas.add("Charlize");
        cadenas.add("Fernando");
        cadenas.add("Belen");
        cadenas.add("Ana");
        cadenas.add("Amy");
        cadenas.add("Adrian");
        cadenas.add("Anama");
        cadenas.add("Cameron");
        cadenas.add("Claudia");
        cadenas.add("Clara");
        cadenas.add("Cristian");
        cadenas.add("Esteban");
        cadenas.add("Estanislao");
        cadenas.add("Pedro");
        cadenas.add("Anahi");
        cadenas.add("Jorge");
        cadenas.add("Francisco");
        cadenas.add("Paula");
        System.out.println("Cantidad de cadenas: " + cadenas.size());
        int i = 0;
        for (i = 0; i < cadenas.size() - 1; i++) {
            String c1 = cadenas.get(i);
            System.out.println("=> " + c1);
            for (int t = i + 1; t < cadenas.size(); t++) {
                String c2 = cadenas.get(t);
                System.out.println("        " + c2 + " = " + computeLevenshteinDistance(c1, c2));
            }
        }





        System.out.println("\n##########Radio:##########");
        mostrar(calcConsultaRango(cadenas, "Alan", 2));
        mostrar(calcConsultaRango(cadenas, "Pablo", 4));
        mostrar(calcConsultaRango(cadenas, "Roberto", 3));
        System.out.println("\n##########NN:##########");
        mostrar(calcConsultaNN(cadenas, "Susana"));
        System.out.println("\n##########NNk:##########");
        mostrar(calcConsultaNNk(cadenas, "Florencia", 4));
    }

    private static int minimum(int a, int b, int c) {
        if (a <= b && a <= c) {
            return a;
        }
        if (b <= a && b <= c) {
            return b;
        }
        return c;
    }

    public static int computeLevenshteinDistance(String str1, String str2) {
        return computeLevenshteinDistance(str1.toLowerCase().toCharArray(), str2.toLowerCase().toCharArray());
    }

    private static int computeLevenshteinDistance(char[] str1, char[] str2) {
        int[][] distance = new int[str1.length + 1][str2.length + 1];

        for (int i = 0; i <= str1.length; i++) {
            distance[i][0] = i;
        }
        for (int j = 0; j <= str2.length; j++) {
            distance[0][j] = j;
        }
        for (int i = 1; i <= str1.length; i++) {
            for (int j = 1; j <= str2.length; j++) {
                int a = distance[i - 1][j] + 1;
                int b = distance[i][j - 1] + 1;
                int c = distance[i - 1][j - 1] + ((str1[i - 1] == str2[j - 1]) ? 0 : 1);
                distance[i][j] = minimum(a, b, c);
            }
        }
        return distance[str1.length][str2.length];

    }

    private static ArrayList<String> calcConsultaRango(ArrayList<String> cadenas, String query, int radio) {
        ArrayList<String> resp = new ArrayList<String>();
        System.out.println("\n" + query + "-Radio<=" + radio);
        for (String c : cadenas) {
            int dist = computeLevenshteinDistance(c, query);
            if (0 <= dist && dist <= radio) {
                resp.add("      d(" + c + ")=" + dist);
            }
        }
        return resp;
    }

    private static ArrayList<String> calcConsultaNN(ArrayList<String> cadenas, String query) {
        ArrayList<String> resp = new ArrayList<String>();
        int i = 0;
        while (resp.isEmpty()) {
            resp = calcConsultaRango(cadenas, query, i);
            i++;
        }
        return resp;
    }

    private static ArrayList<String> calcConsultaNNk(ArrayList<String> cadenas, String query, int tam) {
        ArrayList<String> resp = new ArrayList<String>();
        int radio = 0;
        while (resp.size() < tam) {
            resp = calcConsultaRango(cadenas, query, radio);
            radio++;
        }
        return resp;
    }

    private static void mostrar(ArrayList<String> calcConsultaRango) {
        for (String st : calcConsultaRango) {
            System.out.println(st);
        }
    }
}
